914C - Travelling Salesman and Special Numbers - CodeForces Solution

// becoder Submission #undefined @ 1707012947661
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long l, r;
int len, m;
int a[1005];
char b[1005];
int dp[1005][1005][2];
int num[1005];
int se(int x)
{
	int cnt = 0;
	while(x != 1) x = __builtin_popcount(x), ++cnt;
	return cnt;
}
int dfs(int n, bool limit, int cnt)
{
    if (n == 0) return num[cnt] == m - 1;
    if (~dp[n][cnt][limit]) return dp[n][cnt][limit];
    int up;
    int now = 0;
    if (limit) up = a[n];
    else up = 1;
    for (int i = 0; i <= up; ++i) now += dfs(n - 1, limit && (i == a[n]), cnt + (i != 0)), now %= 1000000007;
    return dp[n][cnt][limit] = now;
}
int solve(int x)
{
	if(!m) return 1;
	memset(dp, -1, sizeof(dp));
	len = strlen(b + 1);
	for (int i = 1; i <= len; ++i) a[i] = b[len - i + 1] - '0';
    return dfs(len, 1, 0) - 2 * (m == 1);
}
signed main()
{
    memset(dp, 0xf3, sizeof(dp));
    for (int i = 1; i <= 1000; ++i) num[i] = se(i);
    scanf("%s", b + 1);
    cin >> m;
    cout << solve(0);
}